#pragma once

#include  "iostream"
#include  "vector"
#include  "stack"
#include  "unordered_map"
#include   "queue"

using namespace std;


/**
 611. 有效三角形的个数
中等
459
相关企业
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。


示例 1:

输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:

输入: nums = [4,2,3,4]
输出: 4*
 *
 *
 *todo 这个从后面遍历只需要确定 前面两个相加大于后面的就行
 * 核心：a<=b<=c,当且仅当a+b>c成立可以组成三角形
 * */



int triangleNumber(vector<int> &nums) {
    sort(nums.begin(), nums.end());
    int sum = 0;
    //最起码留三个数
    for (int i = nums.size() - 1; i >= 2; --i) {
        int low = 0;
        int high = i - 1;
        while (low < high) {
            //因为排序好了说明符合条件9 8 7 6 5 4
            if (nums[low] + nums[high] > nums[i]) {
                sum += high - low;
                high--;
            } else {
                low++;
            }
        }
    }

    return sum;
}
